/*
 * @lc app=leetcode.cn id=304 lang=cpp
 *
 * [304] 二维区域和检索 - 矩阵不可变
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;

class NumMatrix
{
    vector<vector<int>> dp;
    vector<vector<int>> matrix;

public:
    NumMatrix(vector<vector<int>> &matrix)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        dp = vector<vector<int>>(
            m, vector<int>(n, 0));
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < n; i++)
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        for (int i = 1; i < m; i++)
            dp[i][0] = dp[i - 1][0] + matrix[i][0];

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = matrix[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
    }

    int sumRegion(int row1, int col1, int row2, int col2)
    {
        const int tmprow = std::max(row1 - 1, 0);
        const int tmpcol = std::max(col1 - 1, 0);
        int ret = dp[row2][col2];
        if (row1 > 0)
        {
            ret -= dp[tmprow][col2];
            if (col1 > 0) // 会多减
            {
                ret += dp[tmprow][tmpcol];
            }
        }
        if (col1 > 0)
        {
            ret -= dp[row2][tmpcol];
        }
        return ret;
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */
// @lc code=end

// int main(int argc, char const *argv[])
// {
//     vector<vector<int>> matrix = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
//     NumMatrix numMatrix(matrix);
//     cout << numMatrix.sumRegion(2, 1, 4, 3) << endl;
//     return 0;
// }


